package com.cn.algorithm02.class13;

import com.cn.algorithm02.class01.Nodea;

/***
 * @author: hels
 * @description: null（空）是二叉搜索树
 * 找到二叉树中是搜索二叉树的最大子树的个数
 **/
public class C06_MaxSubTreeSize {
    public static void main(String[] args) {
        int[] arr = {5, 10, 14, 8, 14, 11, 17, 6};
        Nodea head = Nodea.getNodeInstance(arr);
        Nodea.printTree(head);
        System.out.println(maxSubTreeSize(head));

    }

    public static int maxSubTreeSize(Nodea head) {
        if (head == null) return 0;
        return process(head).maxSubTreeSize;
    }

    public static Info process(Nodea x) {
        if (x == null) return null;
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        // 当前最小值、最大值
        int min = x.value;
        int max = x.value;
        // 当前节点size
        int allSize = 1;
        if (leftInfo != null) {
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
            allSize += leftInfo.allSize;
        }
        if (rightInfo != null) {
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
            allSize += rightInfo.allSize;
        }

        // 最大二叉搜索子树的size
        // ①当前节点不为BST，从左右子树找最大；②当前节点为BST，左右相加+1；
        int p1 = 0;
        if (leftInfo != null) {
            p1 = Math.max(p1, leftInfo.maxSubTreeSize);
        }
        int p2 = 0;
        if (rightInfo != null) {
            p2 = Math.max(p2, rightInfo.maxSubTreeSize);
        }

        int p3 = 0;
        boolean leftIsBst = leftInfo == null ? true : (leftInfo.allSize == leftInfo.maxSubTreeSize);
        boolean rightIsBst = rightInfo == null ? true : (rightInfo.allSize == rightInfo.maxSubTreeSize);
        if (leftIsBst && rightIsBst) {
            boolean leftLessX = leftInfo == null ? true : (leftInfo.max < x.value);
            boolean rightMoreX = rightInfo == null ? true : (x.value < rightInfo.min);
            if (leftLessX && rightMoreX) {
                p3 = p1 + p2 + 1;
            }
        }

        return new Info(Math.max(Math.max(p1, p2), p3), allSize, min, max);
    }

    public static class Info {
        //最大子树的size
        int maxSubTreeSize;
        //当前节点size
        int allSize;
        int min;
        int max;

        public Info(int maxSubTreeSize, int allSize, int min, int max) {
            this.maxSubTreeSize = maxSubTreeSize;
            this.allSize = allSize;
            this.min = min;
            this.max = max;
        }
    }


}
